#ifndef __CAPAINDICES_ARBOLBMAS_ESTRATEGIABORRADO_CPP_
#define __CAPAINDICES_ARBOLBMAS_ESTRATEGIABORRADO_CPP_

/*****************************************************************************
*                     Organizaci�n de Datos - 75.06                          *
*                         C�tedra Lic. Servetto                              *
*            Facultad de Ingenier�a - Universidad de Buenos Aires            *
******************************************************************************/

#include "ArbolBMas.h"
#include <sstream>
#include <iostream>

using namespace std;
using namespace Comun;

namespace CapaIndices
{
	Estrategia::Estrategia(ArbolBMas *arbol, bool multiple){
		Arbol = arbol;
		Multiple = multiple;
	}



	Estrategia::~Estrategia(){
	}

	//// Declaracion de Metodos Privados ////

	void comprobarResultado(Resultado r , int hijoIzquierdo);

	int obtenerIdHijoDerecho(Registro r );

	void insertarResultado(Registro registroDatos, Clave* clave);

	Nodo* navegar(Nodo* padre, list<string> valoresBusqueda, ArbolBMas* arbol, int hijoIzquierdo, Estrategia* estragia);

	bool busquedaRomano(list<Registro> registros,Clave* clave, IArchivo* archivo, list<Nodo*>* camino);

	bool busquedaMonovalente(list<Registro>* registros,Clave* clave, ArbolBMas* arbol, IArchivo* archivo, list<Nodo*>* camino, int hijoIzquierdo);

	//bool busquedaPolivalente(list<Registro> registros,Clave* clave, ArbolBMas* arbol, int hijoIzq, list<Nodo*>* camino);
    bool busquedaPolivalente(list<Registro>* registros,Clave* clave, ArbolBMas* arbol, int hijoIzq, list<Nodo*>* camino);

	Resultado Estrategia::LocalizarClave(Clave *clave){

		Nodo* nodoActual = Arbol->ObtenerNodoRaiz();
		Camino.insert(Camino.end(),nodoActual);

		if (nodoActual ->Contador == 0)
		{
			Resultado resultado;
			resultado.Codigo = ClaveNoEncontrada;

			return resultado;
		}


		// Mientras el nodo actual no sea una hoja, busca en los nodos internos
		// el camino hasta la clave buscada
		while (nodoActual->Tipo != CapaIndices::Hoja)
		{
			for (IteradorDeRegistros i = nodoActual->Registros.begin(); i!= nodoActual->Registros.end();i++)
				(*i).Marcado = false;

			nodoActual = navegar(nodoActual,clave->ValoresBusqueda,Arbol,nodoActual->HijoIzquierdo,this);
			Camino.insert(Camino.end(),nodoActual);
		}

		// ** Busqueda en el nodo hijo **
		bool datoHallado = false;

		if (Arbol->Metadata->Tipo == Romano)
			datoHallado = busquedaMonovalente(&(nodoActual->Registros),clave,Arbol,Arbol->ArchivoDatos,&Camino,nodoActual->HijoIzquierdo);
		// Dependiendo del tipo de dato que contiene el archivo maestro, busca por igualdad o por igual mayor la clave.
		else if (Arbol->Metadata->TipoDato == Monovalente)
			//
			datoHallado = busquedaMonovalente(&(nodoActual->Registros),clave,Arbol,Arbol->ArchivoDatos,&Camino,nodoActual->HijoIzquierdo);
		else
			//JPB se quito la referencia sobre nodoactual->Registros
			datoHallado = busquedaPolivalente(&(nodoActual->Registros),clave,Arbol, nodoActual->HijoIzquierdo,&Camino);

		Resultado resultado;

		if (!datoHallado)
			resultado.Codigo = ClaveNoEncontrada;
		else
			resultado.Codigo = Exito;

		return resultado;
	}

	bool buscarCondiciones(list<Condicion*>* condiciones, IteradorDeMetadatosAtributos iterador, Condicion** mayor, Condicion** menor, IteradorDeMetadatosAtributos ultimo)
	{
		typedef list<Condicion*>::iterator ICOND;

		for (ICOND i = condiciones->begin(); i!=condiciones->end(); i++)
		{
			Condicion* cond = (* i);

			if ( cond->ValorCondicion.Nombre == iterador->Nombre )
			{
				if ( cond->Simbolo == Igual )
				{
					if ( iterador == ultimo )
						return false;
					else
						return buscarCondiciones( condiciones, ++iterador, mayor, menor, ultimo );
				}
				else if ( (cond->Simbolo == Mayor) || (cond->Simbolo == MayorIgual) )
				{
					*mayor = cond;
					return true;
				}
				else if ( (cond->Simbolo == Menor) || (cond->Simbolo == MenorIgual) )
				{
					*menor = cond;
					return true;
				}
			}
		}

		return false;
	}

	bool Estrategia::ObtenerSiguiente(Nodo** padre, Nodo** siguiente){

		/*Registro* reg = NULL;
		bool terminarEnSiguiente = false;

		for (IteradorDeRegistros i =(* padre)->Registros.begin() ; i != (* padre)->Registros.end(); i++)
		{
			Registro* reg2 = &(*i);
			if (i->Marcado)
			{
				reg2->Marcado = false;
				terminarEnSiguiente = true;
			}else if (terminarEnSiguiente)
			{
				reg2->Marcado = true;
				reg = reg2;
				break;
			}
		}



		// Es el ultimo, por lo que el siguiente esta en el siguiente nodo
		if (reg == NULL)
		{
			// Si es -1, indica que no tiene un nodo siguiente
			if ((* padre)->NodoSiguiente == -1)
				return false;

			Arbol->BuscarNodo((* padre)->NodoSiguiente,padre);
			reg = &(* (* padre)->Registros.begin());
		}			*/

		if ((*padre)->NodoSiguiente < 0)
			return false;

		Grupo g = Arbol->ArchivoDatos->LeerGrupo((*padre)->NodoSiguiente);
		*siguiente = new Nodo(g);
		return true;
	}

	bool Estrategia::ObtenerAnterior(Nodo** padre, Nodo** siguiente){
		// Obtiene el anterior
		
		if ((*padre)->NodoAnterior < 0)
			return false;

		Grupo g = Arbol->ArchivoDatos->LeerGrupo((*padre)->NodoAnterior);
		*siguiente = new Nodo(g);
		return true;
	}

	bool Estrategia::VerificarRangoCondicion(Clave *clave, Nodo *nodo, Nodo** padre, Registro* localizador, Nodo** siguiente)
	{
		bool exito = false;

		Condicion* mayor = NULL;
		Condicion* menor = NULL;

		Registro* primero = NULL;
		Registro* ultimo = NULL;

		if (nodo->Registros.size() > 0)
		{
			if (Arbol->Metadata->Tipo == Griego)
			{
				primero = &(* nodo->Registros.begin());
				ultimo = &(* --nodo->Registros.end());			
			}else if ((*padre)->Registros.size() > 0)
			{
				primero = &(*(*padre)->Registros.begin());
				ultimo = &(* --(*padre)->Registros.end());			
			}

		}else
			exito = false;

		// Busca condiciones sobre la clave. Lo hace en forma recursiva: si encuentra una condicion fuerte sobre el primer campo
			// de la clave, recursa sobre el segundo campo en busca de lo mismo hasta encontrar condiciones debiles o el fin de los campos,
			// donde el resultado seria "false", debido a que encontra todas condiciones fuertes sobre la clave por lo que el resultado es
			// unico y no se requiere revisar ningun nodo hermano.
			exito = buscarCondiciones(&clave->OtrasCondiciones->Subcondiciones,Arbol->Metadata->Claves.begin(),&mayor,&menor,--Arbol->Metadata->Claves.end());

		if (!exito)
			return false;

		if (menor != NULL )
		{
			if (mayor != NULL)
			{
				if (primero != NULL)
				{
					if ( !mayor->Analizar(*primero) )
						return false;
					else
					{
						if (menor->Analizar(*primero))
							return ObtenerAnterior(&nodo,siguiente);
						else
							return false;
					}
				}
				else
					{						
						return ObtenerAnterior(&nodo,siguiente);						
					}
			}

			if (primero!=NULL)
				if (menor->Analizar(*primero))
					return ObtenerAnterior(&nodo,siguiente);
				else
					return false;
			else
				return false;
		}

		if (mayor != NULL )
		{
			return ObtenerSiguiente(&nodo,siguiente);			
		}

		cerr << "CapaIndices->Estrageia.cpp->Estrategia::VerificarRangoCondicion(Clave *clave, Nodo *nodo, Nodo** padre, Registro* localizador, Nodo** siguiente)" << endl << "Estado invalido de la aplicacion. No existe ninguna condicion sobre el nodo hallado." << endl;
		throw new exception();
	}

	//// Metodos Privados ////
	void comprobarResultado(Resultado r , int hijoIzquierdo){

		if (r.Codigo == ClaveNoEncontrada)
		{
			cerr << "CapaIndices->Estrategia.cpp->comprobarResultado(Resultado r , int hijoIzquierdo)" << endl << "La clave " << hijoIzquierdo << " no fue encontrada. Mensaje: " << r.mensaje << endl;
			throw new exception();
		}
		else if (r.Codigo == Error )
		{
			cerr << "CapaIndices->Estrategia.cpp->comprobarResultado(Resultado r , int hijoIzquierdo)" << endl << "Se produjo un error al intentar leer el nodo " << hijoIzquierdo << ". Mensaje: " << r.mensaje << endl;
			throw new exception();
		}

	}


	int obtenerIdHijoDerecho(Registro r ){

		// Setea como hijo izquierdo del proximo registro al hijo derecho del registro actual
		for ( IteradorDeAtributos ia = r.Atributos.begin(); ia != r.Atributos.end() ; ia++ )
		{
			Atributo a = *ia;

			if (a.Nombre == "HijoDerecho")
				return atoi(a.Valor.c_str());
		}

		cerr << "Comun->Estrategia.cpp->obtenerIdHijoDerecho(Registro r )" << endl << "No se encontró el hijo derecho en un registro de un nodo interno.";
		throw new exception();
		}

	void insertarResultado(Registro registroDatos, Clave* clave){

		list<Registro>& resultados = (*clave->Resultado);

		resultados.clear();
		// Inserta el resultado en la lista de resultados de la clave
		// TODO: revisar si es mejor ponerlo aparte
		resultados.insert(resultados.begin(),registroDatos);
	}

	list<Atributo>* ExtraerAtributosClave(list<Atributo>* r, list<MetadatosAtributo> camposClave){

		list<Atributo>* atributosDeClave = new list<Atributo>();

		// Obtiene la lista de atributos del registro que estan contenidos en la clave
		for (IteradorDeAtributos j = r->begin(); j!=r->end(); j++)
		{
			Atributo a = *j;

			// Compara el nombre de los atributos de la clave con los del archivo
			// Leyendo la metada del indice
			for ( IteradorDeMetadatosAtributos k = camposClave.begin(); k != camposClave.end(); k++ )
			{
				MetadatosAtributo m = *k;

				// Si hay coincidencia lo agrega a la lista
				if (m.Nombre == a.Nombre)
					atributosDeClave->insert(atributosDeClave->end(),a);
			}
		}

		return atributosDeClave;
	}

	list<Atributo>* ExtraerAtributosClave(Grupo g, list<MetadatosAtributo> camposClave){

		list<Atributo>* atributosDeClave = new list<Atributo>();

		// Obtiene la lista de atributos del registro que estan contenidos en la clave
		for (IteradorDeAtributos j = g.Atributos.begin(); j!=g.Atributos.end(); j++)
		{
			Atributo a = *j;

			// Compara el nombre de los atributos de la clave con los del archivo
			// Leyendo la metada del indice
			for ( IteradorDeMetadatosAtributos k = camposClave.begin(); k != camposClave.end(); k++ )
			{
				MetadatosAtributo m = *k;

				// Si hay coincidencia lo agrega a la lista
				if (m.Nombre == a.Nombre)
					atributosDeClave->insert(atributosDeClave->end(),a);
			}
		}

		return atributosDeClave;
	}

	Nodo* navegar(Nodo* padre, list<string> valoresBusqueda, ArbolBMas* arbol, int hijoIzquierdo, Estrategia* estrategia)
	{
		Nodo* aux;
		bool hallado = false;

		// Busca el siguiente nodo, que es el menor valor presente en el nodo actual que es mayor que V
		for ( IteradorDeRegistros i = padre->Registros.begin(); i!=padre->Registros.end();i++)
		{
			Registro* r = &(*i);
			r->Marcado = false;

			// Condicion de mayor, si es igual est en el nodo hijo derecho, que es el izquierdo
			// del siguiente que a la vez es mayor al buscado.
			CondicionMayor* mayor = new CondicionMayor();

			// Si es mayor, Busca el atributo que contiene el id del nodo hijo
			if( mayor->Analizar(*ExtraerAtributosClave(&(r->Atributos),arbol->Metadata->Claves),valoresBusqueda) )
			{
				r->Marcado = true;
				// Lee el nodo hijo izquierdo y comprueba si el resultado fue exitoso.
				Resultado res = arbol->BuscarNodo(hijoIzquierdo,&aux);

				comprobarResultado(res,hijoIzquierdo);

				hallado = true;

				// Termina la busqueda
				break;
			}

			// Setea como hijo izquierdo del proximo registro al hijo derecho del registro actual
			hijoIzquierdo = obtenerIdHijoDerecho(*r);
		}

		// Si no hallo el nodo, significa que el valor es mayor al mayor de los registros,
		// por lo que lee el nodo hijo derecho del nodo que es el nodo hijo derecho del ultimo registro.
		if (!hallado)
		{
			//Sea m = el numero de punteros en el nodo
			//Sea C = nodo apuntado por Pm
			arbol->BuscarNodo(hijoIzquierdo,&aux);
		}

		return aux;
	}

	bool busquedaMonovalente(list<Registro>* registros,Clave* clave, ArbolBMas* arbol, IArchivo* archivo, list<Nodo*>* camino, int hijoIzquierdo)
	{		
		Registro* primero = &(* registros->begin());
		CondicionIgual* igual = new CondicionIgual();
		CondicionMayor* mayor = new CondicionMayor();

		if (mayor->Analizar(*ExtraerAtributosClave(&(primero->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda) )
		{
			// Marca el menor de los mayores para tener una referencia en la inercion
			primero->Marcado = true;

			Grupo* registroDatos;

			if (hijoIzquierdo == -1)
				return false;
			// Lee el grupo en el archivo de datos
			registroDatos = &(archivo->LeerGrupo(hijoIzquierdo));

			if ( registroDatos->Registros.size() == 0 )
				return false;

			Registro* primeroDatos = &(*registroDatos->Registros.begin());

			bool esIgual = false;

			if (arbol->Metadata->Tipo == Romano)
				esIgual = igual->Analizar(*ExtraerAtributosClave(&(registroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);
			else
				esIgual = igual->Analizar(*ExtraerAtributosClave(&(primeroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);

			if( esIgual )
			{
				// Inserto el grupo que contiene las referencias
				Nodo* n = new Nodo(*registroDatos);	
				camino->insert(camino->end(),n);
				return true;
			}

			return false;
		}

		Registro* anterior = NULL;

		// Busca una coincidencia exacta, ya que el registro contiene una referencia directa al registro de datos
		for( IteradorDeRegistros i = registros->begin(); i!=registros->end(); i++)
		{
			Registro* r = &(*i);
			CondicionIgual* igual = new CondicionIgual();
			CondicionMayor* mayor = new CondicionMayor();
			r->Marcado = false;

			if( igual->Analizar(*ExtraerAtributosClave(&(r->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda) )
			{
				r->Marcado = true;
				Grupo* registroDatos;
				// Lee el grupo en el archivo de datos
				registroDatos = &(archivo->LeerGrupo(obtenerIdHijoDerecho(*r)));

				// Inserto el grupo que contiene las referencias
				Nodo* n = new Nodo(*registroDatos);	
				camino->insert(camino->end(),n);

				return true;
			}
			else if (mayor->Analizar(*ExtraerAtributosClave(&(r->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda) )
			{
				if (anterior != NULL)
				{
					if (arbol->Metadata->Tipo == Griego)
					{
						Grupo* registroDatos;
						// Lee el grupo en el archivo de datos
						registroDatos = &(archivo->LeerGrupo(obtenerIdHijoDerecho(*anterior)));

						if ( registroDatos->Registros.size() == 0 )
							return false;

						Registro* primeroDatos = &(*registroDatos->Registros.begin());

						bool esIgual = false;
						
						if (arbol->Metadata->Tipo == Romano)
							esIgual = igual->Analizar(*ExtraerAtributosClave(&(registroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);
						else
							esIgual = igual->Analizar(*ExtraerAtributosClave(&(primeroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);

						if( esIgual )
						{
							anterior->Marcado = true;
							// Inserto el grupo que contiene las referencias
							Nodo* n = new Nodo(*registroDatos);	
							camino->insert(camino->end(),n);
							return true;
						}
					}
					else
					{
						Grupo* registroDatos;
						// Lee el grupo en el archivo de datos
						registroDatos = &(archivo->LeerGrupo(obtenerIdHijoDerecho(*anterior)));

						if ( registroDatos->Registros.size() == 0 )
							return false;					

						if( igual->Analizar(*ExtraerAtributosClave(*registroDatos,arbol->Metadata->Claves),clave->ValoresBusqueda) )
						{
							anterior->Marcado = true;
							// Inserto el grupo que contiene las referencias
							Nodo* n = new Nodo(*registroDatos);	
							camino->insert(camino->end(),n);
							return true;
						}
					}
				}

				// Marca el menor de los mayores para tener una referencia en la inercion
				r->Marcado = true;
				return false;
			}
			else
				anterior = &(*i);
		}

		if (anterior != NULL)
		{
			if (arbol->Metadata->Tipo == Griego)
			{
				Grupo* registroDatos;
				// Lee el grupo en el archivo de datos
				registroDatos = &(archivo->LeerGrupo(obtenerIdHijoDerecho(*anterior)));

				if ( registroDatos->Registros.size() == 0 )
					return false;

				Registro* primeroDatos = &(*registroDatos->Registros.begin());

				bool esIgual = false;
						
						if (arbol->Metadata->Tipo == Romano)
							esIgual = igual->Analizar(*ExtraerAtributosClave(&(registroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);
						else
							esIgual = igual->Analizar(*ExtraerAtributosClave(&(primeroDatos->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda);

						if( esIgual )
						{
					anterior->Marcado = true;
					// Inserto el grupo que contiene las referencias
					Nodo* n = new Nodo(*registroDatos);	
					camino->insert(camino->end(),n);
					return true;
				}
			}
			else
			{
				Grupo* registroDatos;
				// Lee el grupo en el archivo de datos
				registroDatos = &(archivo->LeerGrupo(obtenerIdHijoDerecho(*anterior)));

				if ( registroDatos->Registros.size() == 0 )
					return false;					

				if( igual->Analizar(*ExtraerAtributosClave(*registroDatos,arbol->Metadata->Claves),clave->ValoresBusqueda) )
				{
					anterior->Marcado = true;
					// Inserto el grupo que contiene las referencias
					Nodo* n = new Nodo(*registroDatos);	
					camino->insert(camino->end(),n);
					return true;
				}
			}
		}

		return false;
	}	

	bool busquedaPolivalente(list<Registro>* registros,Clave* clave, ArbolBMas* arbol, int hijoIzq, list<Nodo*>* camino){

		int hijoIzquierdo = hijoIzq;

		// Busca entre los registros de la hoja el mayor igual, como antes, pero busca el hijo derecho en el archivo maestro.
		for( IteradorDeRegistros i = registros->begin(); i!=registros->end(); i++)
		{
			Registro* r = &(*i);
			CondicionMayor* mayor = new CondicionMayor();
			Grupo* grupoDatos;
			r->Marcado = false;

			if( mayor->Analizar(*ExtraerAtributosClave(&(r->Atributos),arbol->Metadata->Claves),clave->ValoresBusqueda) )
			{
				r->Marcado = true;

				grupoDatos = &arbol->ArchivoDatos->LeerGrupo(hijoIzquierdo);
				Nodo* n = new Nodo(*grupoDatos);				
				camino->insert(camino->end(),n);

				// TODO: Las operaciones deberian devolver algun enumerado de error
				//comprobarResultado()

				for (IteradorDeRegistros i = grupoDatos->Registros.begin(); i != grupoDatos->Registros.end(); i++)
				{
					Registro r = *i;
					list<Atributo>* atributosDeClave = ExtraerAtributosClave(&(r.Atributos),arbol->Metadata->Claves);
					CondicionIgual* igual = new CondicionIgual();

					if( igual->Analizar(*atributosDeClave,clave->ValoresBusqueda) )
					{
						insertarResultado(r,clave);
						return true;
					}
				}

				// La clave tendria que haberse encontrado en este grupo
				return false;
			}else
				hijoIzquierdo = obtenerIdHijoDerecho(*r);
		}

		Grupo* grupoDatos = &arbol->ArchivoDatos->LeerGrupo(hijoIzquierdo);
		Nodo* n = new Nodo(*grupoDatos);		
		camino->insert(camino->end(),n);

		// TODO: Las operaciones deberian devolver algun enumerado de error
		//comprobarResultado()
		
		for (IteradorDeRegistros i = grupoDatos->Registros.begin(); i != grupoDatos->Registros.end(); i++)
		{
			Registro* r = &(* i);

			list<Atributo>* atributosDeClave = ExtraerAtributosClave(&(r->Atributos),arbol->Metadata->Claves);
			CondicionIgual* igual = new CondicionIgual();
			r->Marcado = false;

			if( igual->Analizar(*atributosDeClave,clave->ValoresBusqueda) )
			{
				r->Marcado = true;

				//insertarResultado(*r,clave);
				return true;
			}			
		}


		return false;
	}


}


#endif
